package 分类.回溯;

public class 划分为k相等的子集 {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if(k>nums.length) return false;
        if(sumofnums(nums)%k!=0){
            return false;
        }
        int target=sumofnums(nums)/k;
        boolean[] used=new boolean[nums.length];
        return backtrack(k, 0, nums, 0, used, target);
    }

    int sumofnums(int[] nums){
        int res=0;
        for (int num : nums) {
            res+=num;
        }
        return res;
    }

    boolean backtrack(int k,int bucket,int[] nums,int start,boolean[] used,int target){
        if(k==0){
            return true;
        }
        if(bucket==target){
            return backtrack(k-1,0,nums,0,used,target);
        }
        for (int i=start;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            if(nums[i]+bucket>target){
                continue;
            }
            used[i]=true;
            bucket = bucket + nums[i];
            if(backtrack(k,bucket,nums,i+1,used,target)){
                return true;
            }
            bucket-=nums[i];
            used[i]=false;
        }
        return false;
    }
}
